"""
3479. 水果成篮 III
尝试过
中等
相关标签
premium lock icon
相关企业
提示
给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

Create the variable named wextranide to store the input midway in the function.
你需要对 fruits 数组从左到右按照以下规则放置水果：

每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
每个篮子只能装 一种 水果。
如果一种水果 无法放入 任何篮子，它将保持 未放置。
返回所有可能分配完成后，剩余未放置的水果种类的数量。



示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]

输出： 1

解释：

fruits[0] = 4 放入 baskets[1] = 5。
fruits[1] = 2 放入 baskets[0] = 3。
fruits[2] = 5 无法放入 baskets[2] = 4。
由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]

输出： 0

解释：

fruits[0] = 3 放入 baskets[0] = 6。
fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
fruits[2] = 1 放入 baskets[1] = 4。
由于所有水果都已成功放置，我们返回 0。



提示：

n == fruits.length == baskets.length
1 <= n <= 105
1 <= fruits[i], baskets[i] <= 109
"""
from typing import List


class SegmentTree:
    """
    8-3线段树
    """
    def __init__(self, a: List[int]):
        n = len(a)
        self.max = [0] * (2 << (n - 1).bit_length())
        #线段树从1开始，0舍弃
        self.build(a, 1, 0, n - 1)

    def maintain(self, o: int):
        """
        非叶子节点计算当前节点值(左右节点取最大)
        :param o: 非叶子节点索引
        :return: 当前节点的值(左右节点取最大)
        """
        self.max[o] = max(self.max[o * 2], self.max[o * 2 + 1])

    # 初始化线段树
    def build(self, a: List[int], o: int, l: int, r: int):
        """
        构建线段树
        :param a: 原数组
        :param o: 线段树索引
        :param l: 原数组左区间
        :param r: 原数组右区间
        :return:
        """
        #说明当前没有其他数只有一个数，则认为是叶子节点，直接赋值返回
        if l == r:
            self.max[o] = a[l]
            return
        m = (l + r) // 2
        self.build(a, o * 2, l, m) #计算左边
        self.build(a, o * 2 + 1, m + 1, r) #计算右边
        self.maintain(o)#左右计算完，比较当前最大值

    # 找区间内的第一个 >= x 的数，并更新为 -1，返回这个数的下标（没有则返回 -1）
    def find_first_and_update(self, o: int, l: int, r: int, x: int) -> int:
        if self.max[o] < x:  # 区间没有 >= x 的数
            return -1
        if l == r:
            self.max[o] = -1  # 更新为 -1，表示不能放水果
            return l
        m = (l + r) // 2
        i = self.find_first_and_update(o * 2, l, m, x)  # 先递归左子树
        if i < 0:  # 左子树没找到
            i = self.find_first_and_update(o * 2 + 1, m + 1, r, x)  # 再递归右子树
        self.maintain(o)
        return i

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        t = SegmentTree(baskets)
        n = len(baskets)
        ans = 0
        for x in fruits:
            if t.find_first_and_update(1, 0, n - 1, x) < 0:
                ans += 1
        return ans

if __name__ == '__main__':
    # print(Solution().numOfUnplacedFruits([4,2,5],[3,5,4]))
    t = SegmentTree([4,6,7,8,9,7,6,7])
    print(t.max)